<!DOCTYPE html>
<html lang="zh">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        canvas {
            border: 1px solid black;
            /* background-image: linear-gradient(to right, transparent 90%, #ccc 0),
                linear-gradient(to bottom, transparent 90%, #ccc 0);
            background-size: 8px 8px, 8px 8px; */
        }
    </style>
</head>

<body>
    <input type="button" value="选择" id="selection" />
    <input type="button" value="next" id="next" />
    <input type="button" value="prev" id="prev" />
    <input type="button" value="play" id="play" />
    <div><canvas width="1024" height="300"></canvas></div>
    <script src="rough.js"></script>
    <script>
        const RECT_WIDTH = 30;
        const SPACEING = 5;
        const CANVAS_WIDTH = 1024;
        const CANVAS_HEIGHT = 300;
        const RECT_MAX_HEIGHT = 100;
        const RECT_MIN_HEIGHT = 20;
        const ARROW_TOP = 30;
        class Frame {
            constructor(x, y, w, h, c, v, vx, vy, i, ix, iy, ic, itx, ity) {
                this.x = x;     // 大矩形 x
                this.y = y;     // 大矩形 y
                this.w = w;     // 大矩形 w
                this.h = h;     // 大矩形 h
                this.c = c;     // 大矩形 c
                this.v = v;     // 大矩形 v 即值
                this.vx = vx;   // 值 x
                this.vy = vy;   // 值 y
                this.i = i;     // 索引值
                this.ix = ix;   // 索引矩形 x
                this.iy = iy;   // 索引矩形 y
                this.ic = ic;   // 索引矩形 c
                this.itx = itx; // 索引矩形值 x
                this.ity = ity; // 索引矩形值 y
            }
        }

        class Draw {
            constructor() {
                this.canvas = document.querySelector('canvas');
                this.ctx = document.querySelector('canvas').getContext('2d');
                this.frames = [];
                this.current = 0;
            }
            reset() {
                this.canvas.width = CANVAS_WIDTH;
                this.canvas.height = CANVAS_HEIGHT;
            }
            drawArrow(fx, fy, tx, ty, c) {
                let theta = 30;
                let headlen = 10;
                let angle = Math.atan2(fy - ty, fx - tx) * 180 / Math.PI;
                let a1 = (angle + theta) * Math.PI / 180;
                let a2 = (angle - theta) * Math.PI / 180;
                let topX = headlen * Math.cos(a1);
                let topY = headlen * Math.sin(a1);
                let bottomX = headlen * Math.cos(a2);
                let bottomY = headlen * Math.sin(a2);

                this.ctx.save();
                this.ctx.translate(0, CANVAS_HEIGHT - RECT_MAX_HEIGHT - RECT_WIDTH - ARROW_TOP);
                this.ctx.beginPath();
                let ax = fx - topX;
                let ay = fy - topY;

                this.ctx.moveTo(ax, ay);
                this.ctx.moveTo(fx, fy);
                this.ctx.lineTo(tx, ty);

                ax = tx + topX;
                ay = ty + topY;
                this.ctx.moveTo(ax, ay);
                this.ctx.lineTo(tx, ty);

                ax = tx + bottomX;
                ay = ty + bottomY;
                this.ctx.lineTo(ax, ay);
                this.ctx.strokeStyle = c || 'black';
                this.ctx.stroke();

                this.ctx.restore();
            }
            drawFrame(idx) {
                this.reset();
                let frame = this.frames[idx];
                frame.a.forEach(x => {
                    this.drawElement(x)
                })
                if (frame.arrowi)
                    this.drawArrow(frame.arrowi.fx, frame.arrowi.fy, frame.arrowi.tx, frame.arrowi.ty, 'blue')
                if (frame.arrowj)
                    this.drawArrow(frame.arrowj.fx, frame.arrowj.fy, frame.arrowj.tx, frame.arrowj.ty)
                if (frame.arrowm)
                    this.drawArrow(frame.arrowm.fx, frame.arrowm.fy, frame.arrowm.tx, frame.arrowm.ty, 'red')
            }
            drawNextFrame() {
                if (this.current + 1 < this.frames.length) {
                    this.drawFrame(++this.current);
                }
            }
            drawPrevFrame() {
                if (this.current - 1 >= 0) {
                    this.drawFrame(--this.current);
                }
            }
            drawElement(r) {
                this.ctx.save();
                this.ctx.translate(0, CANVAS_HEIGHT - RECT_MAX_HEIGHT - RECT_WIDTH);

                this.ctx.fillStyle = r.c;
                this.ctx.beginPath();
                this.ctx.rect(r.x, r.y, r.w, r.h);
                this.ctx.fill();
                this.ctx.lineWidth = .25;
                this.ctx.stroke();

                this.ctx.fillStyle = '#ffffff';
                this.ctx.font = '1em Arial';
                this.ctx.textAlign = 'center';
                this.ctx.fillText(r.v, r.vx, r.vy);

                this.ctx.fillStyle = r.ic;
                this.ctx.beginPath();
                this.ctx.rect(r.ix, r.iy, r.w, r.w);
                this.ctx.fill();
                this.ctx.stroke();

                this.ctx.fillStyle = '#ffffff';
                this.ctx.font = '1em Arial';
                this.ctx.textAlign = 'center';
                this.ctx.fillText(r.i, r.itx, r.ity);

                this.ctx.restore();

            }
            addFrame(obj) {
                let { a, arrowi, arrowj, arrowm, sorted, changeColor } = { ...obj };
                let max = Math.max(...a);
                let min = Math.min(...a);

                const array = [];
                for (let i = 0; i < a.length; i++) {
                    let h = limitHeight(a[i], min, max);
                    let x = i * (RECT_WIDTH + SPACEING);
                    let y = RECT_MAX_HEIGHT - h;
                    array.push(new Frame(
                        x, y, RECT_WIDTH, h, changeColor && changeColor.has(i) ? '#9932CC' : '#007bff',
                        a[i], x + RECT_WIDTH / 2, y + h / 2 + 6,
                        i, x, RECT_MAX_HEIGHT + SPACEING, '#28a745', x + RECT_WIDTH / 2, RECT_MAX_HEIGHT + SPACEING + RECT_WIDTH / 2 + 3
                    ));
                }
                if (sorted >= 0) {
                    for (let i = 0; i < sorted; i++) {
                        array[i].c = 'black';
                    }
                }
                const frame = {};
                frame.a = array;
                if (arrowi) {
                    let e = array[arrowi.i];
                    let y = - ARROW_TOP - RECT_MIN_HEIGHT;
                    array.push(new Frame(e.x, y, RECT_WIDTH, RECT_MIN_HEIGHT, 'blue',
                        "i", e.vx, y + RECT_MIN_HEIGHT / 2 + 6
                    ));

                    frame.arrowi = arrowi;
                    arrowi.fx = arrowi.tx = array[arrowi.i].x + RECT_WIDTH / 2;
                    arrowi.fy = 0;
                    arrowi.ty = array[arrowi.i].y + ARROW_TOP;
                }
                if (arrowj) {
                    let e = array[arrowj.i];
                    let y = - ARROW_TOP - RECT_MIN_HEIGHT;
                    array.push(new Frame(e.x, y, RECT_WIDTH, RECT_MIN_HEIGHT, 'black',
                        "j", e.vx, y + RECT_MIN_HEIGHT / 2 + 6
                    ));

                    frame.arrowj = arrowj;
                    arrowj.fx = arrowj.tx = array[arrowj.i].x + RECT_WIDTH / 2;
                    arrowj.fy = 0;
                    arrowj.ty = array[arrowj.i].y + ARROW_TOP;
                }
                if (arrowm) {
                    let y = - ARROW_TOP - RECT_MIN_HEIGHT - RECT_MIN_HEIGHT - 30

                    let e = array[arrowm.i];
                    array.push(new Frame(e.x, y, RECT_WIDTH, RECT_MIN_HEIGHT, 'red',
                        "min", e.vx, y + RECT_MIN_HEIGHT / 2 + 6
                    ));

                    frame.arrowm = arrowm;
                    arrowm.fx = arrowm.tx = array[arrowm.i].x + RECT_WIDTH / 2;
                    arrowm.fy = - RECT_MIN_HEIGHT - 30;
                    arrowm.ty = - RECT_MIN_HEIGHT;
                }
                this.frames.push(frame);
            }
            clearFrames(a) {
                this.frames = [];
                this.addFrame({ a: a });
                this.current = 0;
            }
            playFrames() {
                if (this.current == this.frames.length - 1) {
                    return;
                }
                this.drawFrame(++this.current);
                setTimeout(() => {
                    this.playFrames();
                }, 300);
            }
        }

        const dd = new Draw();
        const a = [3, 2, 4, 1, 6, 5, 7];

        function createArrow(i, v, blanki, reverse) {
            let arrow = {};
            arrow.i = i;
            arrow.v = v;
            arrow.blanki = blanki;
            arrow.reverse = reverse || false;
            return arrow;
        }

        function selection(a) {
            dd.clearFrames(a);
            let arrow = {};
            for (let i = 0; i < a.length - 1; i++) {
                let min = i;
                dd.addFrame({ a: a, arrowi: createArrow(i), arrowm: createArrow(min), sorted: i });
                for (let j = min + 1; j < a.length; j++) {
                    dd.addFrame({ a: a, arrowi: createArrow(i), arrowj: createArrow(j), arrowm: createArrow(min), sorted: i });
                    if (a[j] < a[min]) {
                        min = j;
                        dd.addFrame({ a: a, arrowi: createArrow(i), arrowj: createArrow(j), arrowm: createArrow(min), sorted: i });
                    }
                }
                if (i != min) {
                    let changeColor = new Set().add(i).add(min);
                    dd.addFrame({ a: a, arrowi: createArrow(i), arrowm: createArrow(min), sorted: i, changeColor: changeColor });
                    swap(a, min, i);
                    dd.addFrame({ a: a, arrowi: createArrow(i), arrowm: createArrow(min), sorted: i, changeColor: changeColor });
                }
            }
            dd.addFrame({ a: a, sorted: a.length });
        }

        function swap(a, i, j) {
            let k = a[i];
            a[i] = a[j];
            a[j] = k;
        }

        function limitHeight(v, min, max) {
            return RECT_MIN_HEIGHT + (v - min) / (max - min) * (RECT_MAX_HEIGHT - RECT_MIN_HEIGHT);
        }

        document.getElementById("selection").onclick = function () {
            selection(a);
        }

        document.getElementById("next").onclick = function () {
            dd.drawNextFrame();
        }

        document.getElementById("prev").onclick = function () {
            dd.drawPrevFrame();
        }

        document.getElementById("play").onclick = function () {
            dd.playFrames();
        }

        dd.addFrame({ a: a })
        dd.drawFrame(0)
    </script>
</body>

</html>